package org.datacoder.geocoding.datastructures.rectangles

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.Jurisdiction

class IntervalTree {

    public IntervalTreeNode root
    public int type

    public IntervalTree(Collection<Jurisdiction> jurisdictions, int type){
        this.type = type
        List<GeoInterval> geoIntervals = new ArrayList<GeoInterval>()
        for(juris in jurisdictions){
            geoIntervals.add(juris.toGeoInterval(type))
        }
        root = createNode(geoIntervals)
    }

    public IntervalTreeNode createNode(List<GeoInterval> geoIntervals){
        if(geoIntervals.isEmpty()){
            return null
        }

        IntervalTreeNode itNode = new IntervalTreeNode()
        double min
        double max = -1000

        Collections.sort(geoIntervals, new GeoIntervalStartPointComparator())
        min = geoIntervals.get(0).retrieveMinDoubleValue()
        for(gi in geoIntervals){
            double minDoubleValue = gi.retrieveMinDoubleValue()
            if(max < minDoubleValue){
                max = minDoubleValue
            }
        }

        int numGeoIntervals = geoIntervals.size()
        itNode.center = geoIntervals.get((Integer)(numGeoIntervals/2)).retrieveCenter()

        List<GeoInterval> leftGeoIntervals = new ArrayList<GeoInterval>()
        List<GeoInterval> rightGeoIntervals = new ArrayList<GeoInterval>()

        int i
        for(i = 0; i < numGeoIntervals; i++){
            GeoInterval gi = geoIntervals.get(i)
            if(gi.retrieveMinDoubleValue() > itNode.center){
                break
            }
            if(gi.retrieveMaxDoubleValue() > itNode.center){
                itNode.addGeoInterval(gi)
            }else{
                leftGeoIntervals.add(gi)
            }
        }
        for(; i < numGeoIntervals; i++){
            rightGeoIntervals.add(geoIntervals.get(i))
        }
        itNode.left = createNode(leftGeoIntervals)
        itNode.right = createNode(rightGeoIntervals)
        return itNode
    }

    public Set<Jurisdiction> findIntervalsContainingPoint(double point){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        IntervalTreeNode itNode = root
        while(itNode != null){
            if(point == itNode.center){
                jurisdictions.addAll(GeocodingUtils.convertGeoShapesToJurisdictions(itNode.geoIntervalsByStart))
                break
            }else if(point < itNode.center){
                for(gi in itNode.geoIntervalsByStart){
                    if(gi.retrieveMinDoubleValue() > point){
                        break
                    }
                    jurisdictions.add(gi.juris)
                }
                itNode = itNode.left
            }else{
                for(gi in itNode.geoIntervalsByEnd){
                    if(gi.retrieveMaxDoubleValue() < point){
                        break
                    }
                    jurisdictions.add(gi.juris)
                }
                itNode = itNode.right
            }
        }
        return jurisdictions
    }
}

